package backtracking;

import java.util.Scanner;

/**
 * 
 * @author victor
 * 
 */
public class SaltoCaballoBacktracking {

	/**
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		try {
			int numero = Integer.parseInt( sc.nextLine() );
			
			saltoCaballo(0, 0, numero );
			
		} catch(Exception e){
			;
		}
	}
	
	/**
	 * 
	 * @param f
	 * @param c
	 * @param lado
	 * @return
	 */
	private static boolean saltoCaballo(int f, int c, int lado) {
		int[][] tablero = new int[lado][lado];
		int[] incrX = new int[] { -1, 1, 2, 2, 1, -1, -2, -2 };
		int[] incrY = new int[] { -2, -2, -1, 1, 2, 2, 1, -1 };
		tablero[f][c] = 1;
		boolean hay = buscar(tablero.length * tablero.length, tablero.length, 2, 0, 0, tablero, incrX, incrY);
		if (hay)
			imprimir(tablero);
		return hay;
	}

	/**
	 * 
	 * @param tablero
	 */
	private static void imprimir(int[][] tablero) {
		for (int i = 0; i < tablero.length; i++) {
			for (int j = 0; j < tablero.length; j++)
				System.out.print(((tablero[i][j] < 10) ? " " : "") + tablero[i][j] + "  ");
			System.out.println();
		}
	}

	/**
	 * 
	 * @param n2
	 * @param n
	 * @param i
	 * @param f
	 * @param c
	 * @param recorrido
	 * @param incrX
	 * @param incrY
	 * @return
	 */
	private static boolean buscar(int n2, int n, int i, int f, int c, int[][] recorrido, int[] incrX, int[] incrY) {
		boolean exito = false;
		for (int k = 0; k < 8 && !exito; k++) {
			int nuevaF = f + incrY[k];
			int nuevaC = c + incrX[k];
			if (nuevaF >= 0 && nuevaF < n && nuevaC >= 0 && nuevaC < n)
				if (recorrido[nuevaC][nuevaF] == 0) {
					recorrido[nuevaC][nuevaF] = i;
					if (i == n2)
						exito = true;
					else {
						exito = buscar(n2, n, i + 1, nuevaF, nuevaC, recorrido, incrX, incrY);
						if (!exito)
							recorrido[nuevaC][nuevaF] = 0;
					}
				}
		}
		return exito;
	}

}
